home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / oper_sys / emerald / emrldsys.lha / Kernel / Em / map96.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-08-17  |  9.0 KB  |  396 lines
  1. /* Copyright 1986 Norm Hutchinson.     May not be used for any         *
  2.  * purpose without written permission from the author.               */
  3.  
  4. #include "Kernel/h/assert.h"
  5. #include "Kernel/h/system.h"
  6. #include "Kernel/h/map96.h"
  7.  
  8. #define INITIALSIZE 16
  9.  
  10. #define HASH(key0, key1, key2, map) \
  11.     ((((key0) << 1)  ^ ((key1) >> 3) ^ ((key2) >> 6)) & map->maxIndex)
  12. static void CheckOutHashTable();
  13.  
  14. #define MAXMAPSTANDBY 20
  15. int                nextFreeMap96 = 0;
  16. Map96              standbyMap96s[MAXMAPSTANDBY];
  17.  
  18. #ifdef DEBUGMAP
  19. int inhibitCheck = 0;
  20. #endif
  21.  
  22. Map96 Map96_Create()
  23. {
  24.   register int i;
  25.   register Map96 m;
  26.   register TE96Ptr    entryPtr;
  27.   register int myNil = NIL;
  28.   
  29.   if (nextFreeMap96 > 0) {
  30.     /* Grab one from standby stack */
  31.     m           = standbyMap96s[--nextFreeMap96];
  32.     return m;
  33.   }
  34.  
  35.   /* Allocate a new one */
  36.   m = (Map96) malloc(sizeof(Map96Record));
  37.   m->table = (TE96Ptr) malloc(INITIALSIZE * sizeof(TE96));
  38.   m->maxIndex = INITIALSIZE - 1;
  39.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  40.   m->count = 0;
  41.   i = m->maxIndex;
  42.   entryPtr = &m->table[i+1];
  43.   do {
  44.       (--entryPtr)->key0 = myNil;
  45.   } while (--i >= 0);
  46. #ifdef DEBUGMAP
  47.       CheckOutHashTable(m);
  48. #endif DEBUGMAP
  49.   return(m);
  50. }
  51.  
  52. Map96 Map96_CreateSized(fCount)
  53. int fCount;
  54. {
  55.   register int i;
  56.   register Map96 m;
  57.   register TE96Ptr    entryPtr;
  58.   register int myNil = NIL;
  59.   
  60.   assert(fCount > 0);
  61.   m = (Map96) malloc(sizeof(Map96Record));
  62.   /* Make i the first power of two greater than fCount */
  63.   for (i = 1; i <= fCount; i += i);
  64.   i--;  
  65.   m->maxIndex = i;
  66.   m->maxCount = m->maxIndex - (m->maxIndex >> 2); /* Max fill 87.5 % */
  67.   m->count = 0;
  68.   m->table = (TE96Ptr) malloc((unsigned)((m->maxIndex+1) * sizeof(TE96)));
  69.   entryPtr = &m->table[i+1];
  70.   do {
  71.       (--entryPtr)->key0 = myNil;
  72.   } while (--i >= 0);
  73. # ifdef lint
  74.   CheckOutHashTable(m);
  75. #endif  
  76. #ifdef DEBUGMAP
  77.   CheckOutHashTable(m);
  78. #endif DEBUGMAP
  79.   return(m);
  80. }
  81.  
  82. void Map96_Clear(m)
  83. register Map96 m;
  84. {
  85.   register int i;
  86.   register TE96Ptr entryPtr;
  87.   register int myNil = NIL;
  88.   
  89.   m->count      = 0;
  90.   i             = m->maxIndex;
  91.   entryPtr      = &m->table[i+1];
  92.   do {
  93.       (--entryPtr)->key0 = myNil;
  94.   } while (--i >= 0);
  95. }
  96.  
  97. void Map96_Destroy(m)
  98. register Map96 m;
  99. {
  100.   register int i;
  101.   register TE96Ptr entryPtr;
  102.   register int myNil = NIL;
  103.   
  104.   if (m == (Map96) NULL) return;
  105.   if ((nextFreeMap96 < MAXMAPSTANDBY)
  106.     && (m->maxIndex == INITIALSIZE - 1)
  107.   ) {
  108.       if (m->count != 0) {
  109.       /* Reinitialize it */
  110.           m->count = 0;
  111.           i = m->maxIndex;
  112.       entryPtr = &m->table[i+1];
  113.       do {
  114.           (--entryPtr)->key0 = myNil;
  115.       } while (--i >= 0);
  116.       }
  117.       
  118.       /* Nice map, recycle it */
  119.       standbyMap96s[nextFreeMap96++] = m;
  120. #ifdef DEBUGMAP
  121.       CheckOutHashTable(m);
  122. #endif DEBUGMAP
  123.       return;
  124.   }
  125. #ifdef DEBUGMAP
  126.   CheckOutHashTable(m);
  127. #endif DEBUGMAP
  128.   free((char *)m->table);
  129.   free((char *)m);
  130. }
  131.  
  132. static void ExpandHashTable(m)
  133. register Map96 m;
  134. {
  135.   register TE96 *nh, *oe, *ne;
  136.   register int oldHashTableSize = m->maxIndex + 1, i;
  137.   register int index;
  138.   register int key0, key1, key2;
  139.  
  140.   m->maxIndex = oldHashTableSize * 2 - 1;
  141.   m->maxCount = m->maxIndex - (m->maxIndex >> 2);
  142.   nh = (TE96Ptr) malloc((unsigned)(oldHashTableSize * 2 * sizeof(TE96)));
  143.   for (i = 0; i <= m->maxIndex; i++) nh[i].key0 = NIL;
  144.   for (i = 0; i < oldHashTableSize; i++) {
  145.     oe = &m->table[i];
  146.     key0 = oe->key0;
  147.     if (key0 == NIL) continue;
  148.     key1 = oe->key1;
  149.     key2 = oe->key2;
  150.     index = HASH(key0, key1, key2, m);
  151.     while (1) {
  152.       ne = &nh[index];
  153.       if (ne->key0 == NIL) {
  154.     ne->key0 = oe->key0;
  155.     ne->key1 = oe->key1;
  156.     ne->key2 = oe->key2;
  157.     ne->value = oe->value;
  158.     break;
  159.       } else {
  160.     index++;
  161.     if (index > m->maxIndex) index = 0;
  162.       }
  163.     }
  164.   }
  165.   free((char *)m->table);
  166.   m->table = nh;
  167. #ifdef DEBUGMAP
  168.   CheckOutHashTable(m);
  169. #endif DEBUGMAP
  170. }
  171.  
  172. int Map96_Lookup(m, key0, key1, key2)
  173. register Map96 m;
  174. register int key0, key1, key2;
  175. {
  176.   register int index = HASH(key0, key1, key2, m);
  177.   register TE96Ptr e;
  178.   register int myNil = NIL;
  179.   register int limit = m->maxIndex;
  180.   
  181. #ifdef DEBUGMAP
  182.   CheckOutHashTable(m);
  183. #endif DEBUGMAP
  184.   e = &m->table[index];
  185.   while (1) {
  186.     if (e->key0 == myNil) {        /* we did not find it */
  187.       return (myNil);
  188.     } else if (e->key0 == key0 && e->key1 == key1 && e->key2 == key2) {
  189.       return (e->value);
  190.     }
  191.     e++;
  192.     if (++index > limit) {
  193.     index = 0;
  194.         e = &m->table[0];
  195.     }
  196.   }
  197. }
  198.  
  199. #ifdef DO_REVERSE
  200. int Map96_InverseLookup(m, value)
  201. register Map96 m;
  202. register int value;
  203. /* do the inverse mapping; if ambiguous return any one of possible values */
  204. /* WARNING: Highly inefficient -- linear search */
  205. {
  206.   register TE96Ptr e, last;
  207.  
  208. #ifdef DEBUGMAP
  209.   CheckOutHashTable(m);
  210. #endif DEBUGMAP
  211.   for (last = &m->table[m->maxIndex+1], e = &m->table[0]; e != last; e++) {
  212.       if ((e->key != NIL) && (e->value == value)) return (e->key);
  213.   }
  214.   return ((int) NIL);
  215. }
  216. #endif DO_REVERSE
  217.  
  218. void Map96_Delete(m, key0, key1, key2)
  219. register Map96 m;
  220. register int key0, key1, key2;
  221. /* Remove the entry, if it is there */
  222. {
  223.   register int index = HASH(key0, key1, key2, m);
  224.   register int value;
  225.   register TE96Ptr e;
  226.  
  227.   while (1) {
  228.     e = &m->table[index];
  229.     if (e->key0 == NIL) {        /* we did not find it */
  230. #ifdef DEBUGMAP
  231.       CheckOutHashTable(m);
  232. #endif DEBUGMAP
  233.       return;
  234.     }
  235.     if (e->key0 == key0 && e->key1 == key1 && e->key2 == key2) {
  236.       /* Found it, now remove it */
  237.       m->count--;
  238.       e->key0 = NIL;
  239.       e->value = NIL;
  240. #ifdef DEBUGMAP
  241.       inhibitCheck = 1;
  242. #endif
  243.       while (1) {
  244.     /* rehash until we reach nil again */
  245.     if (++index > m->maxIndex) index = 0;
  246.     e = & m->table[index];
  247.     key0 = e->key0;
  248.     if (key0 == NIL) {
  249. #ifdef DEBUGMAP
  250.         inhibitCheck = 0;
  251.         CheckOutHashTable(m);
  252. #endif DEBUGMAP
  253.         return;
  254.     }
  255.     key1 = e->key1;
  256.     key2 = e->key2;
  257.     /* rehashing is done by removing then reinserting */
  258.     value = e->value;
  259.     e->key0 = e->value = NIL;
  260.     m->count--;
  261.     Map96_Insert(m, key0, key1, key2, value);
  262.       }
  263.     }
  264.     if (++index > m->maxIndex) index = 0;
  265.   }
  266. }
  267.  
  268. void Map96_Insert(m, key0, key1, key2, value)
  269. register Map96 m;
  270. register int key0, key1, key2, value;
  271. {
  272.   register int index;
  273.   register TE96Ptr e;
  274.   assert(key0 != NIL);
  275.   if (m->count >= m->maxCount) ExpandHashTable(m);
  276.   index = HASH(key0, key1, key2, m);
  277.   while (1) {
  278.     e = &m->table[index];
  279.     if (e->key0 == NIL) {        /* put it here */
  280.       e->key0 = key0;
  281.       e->key1 = key1;
  282.       e->key2 = key2;
  283.       e->value = value;
  284.       m->count++;
  285. #ifdef DEBUGMAP
  286.       CheckOutHashTable(m);
  287. #endif DEBUGMAP
  288.       return;
  289.     } else if (e->key0 == key0 && e->key1 == key1 && e->key2 == key2) {
  290.       e->value = value;
  291. #ifdef DEBUGMAP
  292.       CheckOutHashTable(m);
  293. #endif DEBUGMAP
  294.       return;
  295.     }
  296.     if (++index > m->maxIndex) index = 0;
  297.   }
  298. }
  299.  
  300. int Map96_FindNext(m, startIndex, key0Ptr, key1Ptr, key2Ptr, valuePtr)
  301. register Map96 m;
  302. int *startIndex;
  303. int *key0Ptr, *key1Ptr, *key2Ptr, *valuePtr;
  304. {
  305.   register int i;
  306.   register TE96Ptr e;
  307.   for (i = *startIndex; i <= m->maxIndex; i++) {
  308.     e = &m->table[i];
  309.     if (e->key0 != NIL) {
  310.       *key0Ptr = e->key0;
  311.       *key1Ptr = e->key1;
  312.       *key2Ptr = e->key2;
  313.       *valuePtr = e->value;
  314.       *startIndex = i + 1;
  315.       return(1);
  316.     }
  317.   }
  318.   *key0Ptr = NIL;
  319.   *key1Ptr = NIL;
  320.   *key2Ptr = NIL;
  321.   *valuePtr = NIL;
  322.   *startIndex = -1;
  323.   return(0);
  324. }
  325.  
  326. void Map96_Print(m)
  327. register Map96 m;
  328. {
  329.     int key0, key1, key2, value, index;
  330.     printf(
  331.     "\nDump of map96 @ 0x%05x, %d entr%s, current max %d\nIndex\tKey0\t\tKey1\t\tKey2\t\tValue\n",
  332.     m, m->count, m->count == 1 ? "y" : "ies",  m->maxCount);
  333.     for (index = 0; index <= m->maxIndex; index++) {
  334.     key0 = m->table[index].key0;
  335.     key1 = m->table[index].key1;
  336.     key2 = m->table[index].key2;
  337.     value = m->table[index].value;
  338.     printf("%3d\t0x%08.8x\t0x%08.8x\t0x%08.8x\t0x%08.8x\n", index, 
  339.         key0, key1, key2, value);
  340.     }
  341. }
  342.  
  343. static void CheckOutHashTable(m)
  344. register Map96 m;
  345. {
  346.   register int i;
  347.   register TE96Ptr realElement, e;
  348.   register int index, firstIndex, count;
  349.   count = 0;
  350.  
  351. #ifdef DEBUGMAP
  352.   if (inhibitCheck) return;
  353. #endif
  354.   for (i = 0; i <= m->maxIndex; i++) {
  355.     realElement = &m->table[i];
  356.     if (realElement->key0 != NIL) {
  357.       count++;
  358.       index = HASH(realElement->key0, realElement->key1, realElement->key2, m);
  359.       firstIndex = index;
  360.       while (1) {
  361.     e = &m->table[index];
  362.     if (e->key0 == NIL) {        /* we did not find it */
  363.       break;
  364.     } else if (e->key0 == realElement->key0 && 
  365.            e->key1 == realElement->key1 && 
  366.            e->key2 == realElement->key2) {
  367.       break;
  368.     } else {
  369.       index++;
  370.       if (index > m->maxIndex) index = 0;
  371.       if (index == firstIndex) {
  372.         index = -1;
  373.         break;
  374.       }
  375.     }
  376.       }
  377.       
  378.       if (index == -1 || !(e->key0 == realElement->key0 &&
  379.                e->key1 == realElement->key1 &&
  380.                e->key2 == realElement->key2)) {
  381.       printf(
  382.         "Map96 problem: Key 0x%x 0x%x 0x%x, rightI %d, realI %d probI %d value 0x%x\n",
  383.         realElement->key0, realElement->key1, realElement->key2,
  384.         firstIndex, i, index, realElement->value);
  385.       Map96_Print(m);
  386.       }
  387.     }
  388.   }  
  389.   if (count != m->count) {
  390.     printf(
  391.       "Map96 problem: Should have %d entries, but found %d.\n", m->count,
  392.       count);
  393.     Map96_Print(m);
  394.   }
  395. }
  396.